#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/28 21:02
# @USER    : Shengji He
# @File    : MinimumSizeSubarraySum.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        """
        Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous
        subarray of which the sum ≥ s. If there isn't one, return 0 instead.

        Example:
            Input: s = 7, nums = [2,3,1,2,4,3]

            Output: 2

            Explanation: the subarray [4,3] has the minimal length under the problem constraint.

        Follow up:
            If you have figured out the O(n) solution, try coding another solution of which the time complexity
            is O(n log n).

        :param s:
        :param nums:
        :return:
        """
        if not nums:
            return 0

        ans = len(nums) + 1
        start, end = 0, 0
        total = 0
        while end < len(nums):
            total += nums[end]
            while total >= s:
                ans = min(ans, end - start + 1)
                total -= nums[start]
                start += 1
            end += 1
        return 0 if ans == len(nums) + 1 else ans


if __name__ == '__main__':
    S = Solution()
    s = 7
    nums = [2, 3, 1, 2, 4, 3]
    print(S.minSubArrayLen(s, nums))
    print('done')
